The present invention relates to the transmission and reception of signals, and more particularly, to methods and apparatus for optimizing the equalization of a signal that has been transmitted through a distorting medium.
Modern modems, and in particular ADSL modems with a DMT line code, generally employ block-based modulation to transmit data across a twisted pair. In such systems equalization of the received signal is necessary to ensure that as much of the energy of the overall impulse response as possible is contained in a fixed number of symbol periods, called the cyclic prefix of the system. The equalization process is typically performed in two stages, the initial stage and the steady state. In the initial stage, a predetermined signal is transmitted in order to study the impulse response of the transmission channel and determine the equalizing coefficients. In the steady state, any signal may be transmitted, and the equalization coefficients are applied as a finite impulse response (FIR) filter to the signal received by the receiver.
While steady state operation is straightforward, determining the equalization coefficients, also referred to as xe2x80x9cequalizing the channel,xe2x80x9d is less so. Proposed methods for determining the equalizing coefficients in a DMT system are either computationally complex, and therefore require an enormous amount of computer memory and processing time in order to implement them, or they suffer from inaccuracies due to non-optimized algorithms or due to computational roundoff errors that arise when performing operations such as division on a DSP.
Methods of the prior art generally comprise two major parts:
Preparing the parameters for the algorithm, including computation of auto-correlation and cross-correlation matrices; and
Iteratively performing computations on a certain range of delays in order to find an optimum delay such that the overall signal contained in the corresponding response region will have maximal energy.
Most of the computational effort is generally required for the iterative computations as the preparation is performed only once.
U.S. Pat. No. 5,461,640 describes a method where the auto-correlations and cross-correlations are computed during the parameter preparation part. U.S. Pat. No. 5,461,640 is disadvantageous in that it presents computational complexities, discussed hereinbelow, that might be avoided during the iterative computation part were another method used during the parameter preparation part.
To understand the equalization problem we may denote an input signal xk, an output signal yk, a channel response by h, and equalizer taps w. Thus the overall response of the channel may be expressed as:
{tilde over (h)}=h*w,
We may further denote {tilde over (b)} as the ideal overall response which is equivalent to the overall response {tilde over (h)} in the response region, and zero outside the response region, and denote {tilde over (b)} as the filter which is the non-zero portion of the ideal overall response {tilde over (b)}.
Two prior art approaches are now described.
1. In one approach, methods used for optimization of decision feedback equalization (DFE) are employed, where the equalizer taps w is the forward filter, and the filter b is the feedback filter. The only difference is that in the DMT case b does not have to be monic and causal. That is, the first tap does not have to be constrained to unity. The following algorithm is proposed:
a) Estimate the cross-correlation between the channel input xk, and the channel output yk, and the auto-correlation of the output yk.
b) For delay xcex94=xcex94min to xcex94max for i=1 to v
(i) Constrain the i-th tap of b to be unity
(ii)       minimize    ⁢          xe2x80x83        ⁢                  "LeftDoubleBracketingBar"                              b            ~                    -                      h            ~                          "RightDoubleBracketingBar"            2        ⁢      xe2x80x83  
xe2x80x83using the DFE minimization techniques.
c) Choose the minimum of all the solutions found.
2. Another approach, such as is described in U.S. Pat. No. 5,461,640, tries to minimize the ratio of the energy in the output of the ideal response filter to the energy in the output of the overall response filter that is outside the response region. This is accomplished by applying a constraint of the form:
∥b∥2=1,
where b has a length v, and minimizing
zTRuuz
where Ruu is a matrix comprising the auto-correlations of the inputs xk, the outputs of the channel yk, and the cross-correlations between them, and z is a vector comprising the filter b and the equalizer taps w. The computations that follow require solving an eigenvalue problem for a matrix whose dimensions are (m+v) by (m+v), where m is the number of taps in the equalizer, and v the length of the time region allowed for the response region (in DMT systems v is the cyclic prefix+1). This eigenvalue problem is solved for each possible delay, and after performing the computation for all possible delays the global minimum is chosen.
Some straightforward manipulations transform the problem from an (m+v) by (m+v) size eigenvalue problem to a v by v size problem by performing a matrix inversion and multiplication of matrices of sizes m by m and m by v at each stage, and, moreover, by introducing division at each stage.
In the first approach 1) described above, each iteration of step b) requires the formation of two new matrices and the performing of a matrix inversion, usually leading to an enormous number of calculations for each xcex94 tried.
The second approach 2) greatly relaxes the computation load by performing only one matrix inversion and solving one maximal eigenvalue problem for each xcex94. However, as stated above, the matrices involved are still quite large, and even after simplification methods are used a matrix inversion of size m by m must be performed at each stage. The formation of a v by v size matrix at each step involves computations with larger size m by m matrices if v less than =m, and an eigenvalue problem of size v by v (or perhaps a generalized eigenvalue problem) must be solved, which is very inefficient where v greater than m.
Relevant methods useful in equalization are discussed in xe2x80x9cFundamentals of Matrix Computationsxe2x80x9d by D. S. Watkins, John Wiley and Sons, 1991.
U.S. Pat. No. 5,285,474 is also believed to be representative of the art.
The disclosures of all U.S. Patents and publications mentioned in this specification and of U.S. patents and publications cited therein are hereby incorporated by reference.
The present invention seeks to provide novel apparatus and methods for determining equalizer coefficients which overcomes disadvantages of the prior art as discussed above. Other objects and advantages of the invention will become apparent from the description and claims which follow taken together with the appended drawings.
In accordance with the present invention there is provided a method for calculating a vector A from a set comprising at least one pair of subspaces of RN wherein N is the dimension of said vector space, each of the at least one pair comprises a first subspace and a second subspace of the vector space RN, and a set of maximal projections and their corresponding unit vectors, each of said maximal projections is associated with one of the pairs of subspaces, wherein for each of the pairs of subspaces the first subspace is the column space of a N by m matrix M and the second subspace is a function of a predefined set of indices between 1 and N, comprising:
for each of the pairs of subspaces:
determining a unit vector C in one of said subspaces so that a projection of the unit vector upon another of the vector subspaces is maximal for all unit vectors in one of the vector subspaces;
applying a predefined optimizing function to the set of maximal projections and unit vectors, thereby selecting a maximal projection and its corresponding unit vector and pair of first and second subspaces;
determining a vector A having length m, so that the product of vector A and matrix M is a unit vector B and the projection of B upon second subspace in the pair corresponding to said selected maximal projection is equal to the selected maximal projection.
The present invention further provides a method which adapts the computations to be performed according to the input data for the equalizing problem. The method includes generating a digital training signal and sending it through a channel, estimating the channel impulse response using the input and received signal and forming an approximation matrix, computing an orthonormal basis for the columns of the approximation matrix, and finding the projection of the vector space generated by this basis on the response region or finding the projection of the response region on the vector space generated by the columns of the approximation matrix. As will be used hereinafter the term approximation matrix will be used to denote a matrix M, whose product with any vector (x1, x2, x3, . . . , xm)T of length m, is an approximation to the channel""s response to a mT duration input digital signal, where T is the sampling period of the digital signal, and the values of the signal at times T, 2T, . . . , mT, are equal to x1, x2, x3, . . . , xm respectively.
The term xe2x80x9cresponse regionxe2x80x9d will be used hereinafter to denote a subspace of RN which coordinates other than in a predefined set of indices, are equal to zero. Typically, the predefined set of indices will comprise v=cyclic prefix+1 consecutive integers.
The term xe2x80x9cmaximal projectionxe2x80x9d used in conjunction with projection of one subspace of RN upon another subspace of RN will be used hereinafter to denote the maximal scalar product obtained from multiplying two unit vectors, one from each of the two subspaces.
Choosing which projection to perform depends on the dimensions of the vector spaces involved. Thus, when v less than =m, computations for an eigenvalue problem of size v by v are performed, and where v greater than m, computations for an eigenvalue problem of size m by m are performed. The methods of the present invention are suited to be implemented either by a programmable DSP, a dedicated ASIC, or a general purpose computer. Finally, a set of equalizer coefficients is generated.
In accordance with a preferred embodiment of the present invention, the step of determining a unit vector C in the method provided, comprises:
forming matrices Q and R from an orthonormal basis to the column space of said matrix M wherein Q has the same dimensions as M, wherein the columns of Q are orthonormal, and wherein either of Q=MR and QR=M are true;
generating the unit vector C in the first subspace, wherein the unit vector is associated with a maximal projection upon the second subspace; and
determining the maximum projection from the unit vector C.
More preferably, in the method provided, the step of determining a vector A comprises generating vector A by:
determining a vector of coordinates of the unit vector C associated with a basis which elements are equal to the columns of Q; and
multiplying the vector of coordinates of the unit vector C by the matrix R where Q=MR and by Rxe2x88x921 where QR=M.
According to another embodiment of the present invention, the step of determining a unit vector C step in the method provided, comprises:
forming matrices Q and R from an orthonormal basis to the column space of said matrix M wherein Q has the same dimensions as M, wherein the columns of Q are orthonormal, and wherein either of Q=MR and QR=M are true;
generating said unit vector C in said second subspace, second subspace being the subspace of RN whose coordinate values other than in said predefined set of indices are zero, wherein said unit vector is associated with a maximal projection upon said first subspace; and
determining said maximum projection from said unit vector C.
More preferably, the step of determining vector A comprises generating the vector by:
determining a vector of coordinates of the unit vector C associated with a standard basis of said second subspace; and
multiplying the vector of coordinates of the unit vector C by RQxcex94T where Q=MR and by Rxe2x88x921Qxcex94T where QR=M, where Qxcex94 is a matrix comprising rows of Q corresponding to the predefined set of indices and normalizing the result thus obtained to a unit vector.
Additionally in accordance with a preferred embodiment of the present invention the forming matrices step of the method provided, includes forming matrices Q and R by using Gram-Schmidt orthogonalization.
Moreover in accordance with yet another preferred embodiment of the present invention the forming matrices step of the method provided, includes forming matrices Q and R by using QR decomposition.
According to another aspect of present invention, there is provided a method for optimizing an equalizer in a data transmission system, where the equalizer is used to equalize a signal transmitted through a distorting channel. This method comprises the steps of:
transmitting a known training signal through the distorting channel;
generating a replica of the known training signal;
generating an N by m approximation matrix M from the output of the transmitted signal and the replica of the known training signal;
for each delay in a predefined range of delays:
generating a pair of a first subspace and a second subspace of a vector space RN, the first subspace is the column space of said matrix M and the second subspace being a function of said delay is the subspace of RN whose coordinates other than in a predefined set of that delay are zero, comprising:
for each of the pair of subspaces:
determining a unit vector C in one of said subspaces so that a projection of the unit vector upon another of said vector subspaces is maximal for all unit vectors in one of the vector subspaces;
applying a predefined optimizing function to the set of maximal projections and unit vectors, thereby selecting a maximal projection and its corresponding unit vector and pair of first and second subspaces;
determining a vector A having length m, characterized in that its product with matrix M is a unit vector B and the projection of B upon the second subspace in the pair corresponding to the selected maximal projection is equal to the selected maximal projection; and
setting vector A or any scalar multiplication thereof, to be the vector of equalizer coefficients, thereby optimizing the equalizer.
According to still another aspect of the present invention there is provided a system operative in calculating a vector A from a set comprising at least one pair of subspaces of RN, each of said at least one pair comprises a first subspace and a second subspace of a vector space RN, and a set of maximal projections and their corresponding unit vectors, each of said maximal projection is associated with one of said pair of subspaces, wherein N is the dimension of said vector space, and wherein for each of said pair of subspaces, said first subspace is the column space of a N by m matrix M and said second subspace is a function of a predefined set of indices between 1 and N, comprising:
apparatus operative for each of said pair of subspaces for determining a unit vector C in one of said subspaces so that a projection of said unit vector upon another of said vector subspaces is maximal for all unit vectors in said one of said vector subspaces;
apparatus for applying a predefined optimizing function to said set of maximal projections and unit vectors, thereby selecting a maximal projection and its corresponding unit vector and pair of first and second subspaces; and
apparatus for determining a vector A having length m, characterized in that the product of said vector A and matrix M is a unit vector B and the projection of B upon second subspace in the pair corresponding to said selected maximal projection is equal to said selected maximal projection.
By a preferred embodiment of the invention, there is provided a system for equalizing a signal transmitted through a distorting channel and comprising:
a signal receiver operative to receive an output of a known training signal of data bits transmitted through said channel;
a generator operative to generate a replica of the known training signal;
an approximation matrix generator operative to generate an approximation matrix M from said output of the known training signal and said replica of said training signal;
a generator operative to generate for each delay in a predefined range of delays a pair of a first subspace and a second subspace of a vector space RN, the first subspace is the column space of matrix M and the second subspace being a function of the delay is the subspace of RN whose coordinates other than in a predefined set of that delay are zero, by determining for each of the pair of subspaces a unit vector C in one of the subspaces, where the unit vector C is characterized in that a projection of the unit vector upon another of the vector subspaces is maximal for all unit vectors in one of the vector subspaces;
apparatus for applying a predefined optimizing function to the set of maximal projections and unit vectors, thereby selecting a maximal projection and its corresponding unit vector and pair of first and second subspaces;
apparatus for determining a vector A having length m, so that its product with matrix M is a unit vector B and the projection of B upon second subspace in the pair corresponding to the selected maximal projection is equal to the selected maximal projection; and
apparatus for setting vector A to be the vector of equalizer coefficients, thereby optimizing the equalizing of the signal transmitted through said distorting channel.
Furthermore, the system provided may also include a transmitter operative to transmit the known training signal through the distorting channel.